第13章 並行処理の予備知識

13.1 ハードウェア

プロセッサとスレッド

プロセッサ

命令を実行するハードウェアのユニット

スレッド

逐次的なプログラム

以下の3つの状態がある

実行中

実行可能

ブロック中

同時スレッディング(SMT)、ハイパースレッディングのスレッドとは別物

SMTのスレッドは論理的なコアを指す

スケジューラ

スレッドの状態を変えるやつ

普通はOSの中にいる

マルチプロセッサ

複数のプロセッサを持つコンピュータ

インターコネクト

マルチプロセッサにおける各プロセッサ間の通信経路

共有バス

最も単純

大規模なマルチコアプロセッサでのインターコネクト

メモリリクエストが複数ノードを経由しうる

単一システムバス

コア数が8~16を超えてくるとボトルネックになる

しかし単純で安い

スヌーピングができるのでコヒーレンスをサポートするのが楽

対称的マルチプロセッサ(Symmetric Multiprocessor, SMP)

メモリユニットがプロセッサと分離されている

プロセッサのメモリユニットへのアクセス時間がメモリユニットに依らない

非均一メモリアクセス(non-uniform memory access: NUMA)

メモリが各プロセッサに紐づけられている

メモリ

自明

キャッシュ

キャッシュライン

キャッシュのサイズ 32 or 64 byte

キャッシュの置換ポリシー

キャッシュはメモリ全体の一部分しか保持できないので、広範囲のメモリにアクセスするとキャッシュのどれかを排除する必要がある

フルアソシアティブ

任意のメモリアドレスをキャッシュ上の任意の場所に保管できる

任意のキャッシュラインの集合を保持可能

ダイレクトマップ

あるメモリの部分空間がキャッシュされる位置が一意に定まる

kウェイセットアソシアティブ

あるメモリの部分空間がキャッシュされる位置がk個

犠牲キャッシュ

おそらくマイナー

最近犠牲になったキャッシュを別のキャッシュに入れる

基本はダイレクトマップ

追い出されたやつはフルアソシアティブに入れる

キャッシュのレベル同士の関係

包含的とは低いレベルのキャッシュは必ず高いレベルのキャッシュに含まれている

排他的とはあるラインが2つのレベルのうちどちらかにしか含まれない

コヒーレンス

キャッシュコヒーレンス

マルチプロセッサにおいてはキャッシュの値が食い違う可能性がある

キャッシュの値にある程度の一貫性を持たせる必要がある

MESIコヒーレンスプロトコル

それぞれのキャッシュラインは以下の4つのいずれかの状態をもつ

Modified

このキャッシュだけが、該当するラインの複製を保持しており、そのラインの値は変更されたが、まだメモリに書き戻されていない

Exclusive

このキャッシュだけが、該当するラインの複製を保持しており、そのラインの値はメモリと一致している

Shared

他のキャッシュもこのラインの複製を保持している可能性があるが、すべてメモリ中の値と同じ値である

Invalid

このキャッシュはラインの複製を保持していない

具体的な書き込み, 読み込み

書き込むためには 該当ラインがM or Eである必要があり、書き込み後はMになる

I状態のラインから読み出したいときは

他のプロセッサがMで保持している

書き戻してSまたはIに落とす

他のプロセッサがEで保持している

単にSまたはIに落とす

他のプロセッサがSまたIで保持している

単に読む

I状態のラインに書き込みたいときは

読み出したいときとほぼ同じだが、他のプロセッサのキャッシュはIに落ちる

S状態のラインに書き込みたいときは

他のキャッシュをIに落とす

欠点

プロセッサ数についてスケールしない

最近ではコヒーレンスをソフトウェアに投げるものも出てきている

偽共有

異なるデータが同じキャッシュラインに割り当てられることで、プロセッサ間でキャッシュラインの奪い合いが起こること

例

プロセッサAがアドレス0に書きたい

プロセッサBがアドレス256に書きたい

アドレス0とアドレス256は同じキャッシュラインに配当される

本当は独立して書き込めるのに...

キャッシュコヒーレンスの性能の例: スピンロック

スピンロック

プロセッサがwhileでぐるぐる回りながらロックを待つことから

AtomicExchangeスピンロック

code:AtomicExchange.py

def exchangeLock(x):

while AtomicExchange(x, 1) = 1:

pass # 何もしない

def exchangeUnlock(x):

*x ← 0

def AtomicExchange(x, v):

atomic:

old ← *x

*x ← v

return old

テストアンドテストアンドセット型AtomicExchangeスピンロック

code:TestAndTesAndSetAtomicExchange.py

def testAndTestAndSetExchangeLock(x):

while testAndExchange(x) = 1

pass # 何もしない

def testAndTestAndSetExchangeUnlock(x):

*x ← 0

def testAndExchange(x):

while *x = 1:

pass # 何もしない

return AtomicExchange(x, 1)

このためキャッシュが汚染されない

TestAndSet プリミティブの利用

code: UsageOfTestAndSetPrimitive.py

# これがプリミティブ

def TestAndSet(x):

atomic

old ← *x

if old = 0

*x ← 1

return 0

return 1

def testAndSetLock(x):

while TestAndSet(x) = 1:

pass # 何もしない

def testAndSetUnlock(x):

*x ← 0

def testAndTestAndSetLock(x):

while testAndTestAndSet(x) = 1:

pass # 何もしない

def testAndTestAndSet(x):

# この↓ループがtestAndSetLockとtestAndTestAndSetLockの差異

while *x = 1:

pass # 何もしない

return TestAndSet(x)

def testAndTestAndSetUnlock(x):

testAndSetUnlock(x)

oldが0だった場合にしか書き込みが発生しないのでキャッシュラインが汚染されない

13.2 ハードウェアによるメモリコンシステンシ

共有メモリのコヒーレンスを仮定する

メモリの一つの場所への書き込みは全順序がつく

メモリの複数の場所への書き込みの順序は操作の順序と一致しない

プログラム順序とメモリ順序が一致しない

ハードウェア的な理由

バッファ

複数の書き込みがまとめられる

古い書き込みが新しい書き込みとまとめられて同時にメモリに反映されるケースがある

キャッシュミスによるOut of Order実行

キャッシュミスが起こると現代的なプロセッサはキャッシュミスを起こした命令を飛ばして後の命令を実行する

ソフトウェア的な理由

コンパイラの最適化

全順序より弱いコンシステンシの例

フェンスと事前発生(happens-before)

フェンス命令を超えてメモリアクセスに関する命令は並び替えされない

通常、不可分操作はすべての操作に対する全順序的フェンスとなる

しかし、全順序でないフェンスも考えることができる

例: 獲得-解放

獲得

獲得より後の操作は獲得より前に起こってはいけない

獲得より前の操作は獲得より後に起こっても良い

解放

解放より前の操作は解放より後に起こってはいけない

use after freeみたいなイメージかな

解放より後の操作は解放より前に起こっても良い

獲得(get(x))-解放(release(x))のペアは

............. get(x) ................. release(x) ..................

ペアの外の操作は中に入っても良い

ペアの中の操作は外に出てはいけない

さまざまなコンシステンシモデル

strict consistency

最強

すべての操作がシステムのどの部分から見ても同じ順序で起きる

実装が困難

sequential consistency

グローバルなhappens-before順序は個々のプロセッサのプログラム順序と矛盾しない限り、どんな半順序でも良い

プロセッサ単位でsequential

weak consistency

すべての不可分操作を全順序的フェンスとして扱う

release consistency

上の獲得-解放の例

causal consistency

先行する読み出しと後続する書き込みの間の順序を強制する

relaxed consistency

逐次的コンシステンシより弱いすべて

ハードウェアごとにサポートするコンシステンシモデルが異なる。

少なくともweakとreleaseはサポートする。

x86 は Total Store Order というらしい

https://gyazo.com/5285e7e6adcae77cee9b700916ff6974